package arrays;

public class Solution_1 {
    /**
     * 二分查找 704-力扣
     * @param nums
     * @param target
     * @return
     */
    //这里是用左闭右闭区间的二分查找
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        if (nums[0] > target || nums[right] < target) {
            return -1;
        }
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            }
            if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;

    }

    /**
     * 279. 删除链表中等于给定值 val 的节点 -easy
     * @param nums
     * @param val
     * @return
     * 快慢指针
     */
    public int removeElement(int[] nums, int val) {
        //1.快慢指针
        int k =0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != val) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }

    public int removeElement_1(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while (right >= 0 && nums[right] == val) right--; //将right移到从右数第一个值不为val的位置
        while (left <= right) {
            if (nums[left] == val) { //left位置的元素需要移除
                //将right位置的元素移到left（覆盖），right位置移除
                nums[left] = nums[right];
                right--;
            }
            left++;
            while (right >= 0 && nums[right] == val) right--;
        }
        return left;
    }
}
